// TestSorting.java
// Tests and times the following sorting methods on sorted and unsorted arrays
// of various sizes:
//      InsertionSort.insertionSort(int[] list)
//      QuickSort.quickSort(int[] list)
//      RadixSort.radixSort(int[] array)
//
// by Jeff Ward

import java.util.*;
import java.io.*;

public class TestSorting {
	private static PrintWriter outFile;

	public static void main(String[] args) throws IOException {
		outFile = new PrintWriter("Timings.txt");

		int[] sizes = { 100000, 200000 };

		for (int n : sizes) {
			int[] orderedArray = generateOrdered(n);
			int[] randomArray = generateRandom(n);
			int[] copy;

			// Insertion sort tests
			testInsertionSort(orderedArray, true);
			copy = copyArray(randomArray);
			testInsertionSort(copy, false);

			// Quick sort tests
			testQuickSort(orderedArray, true);
			copy = copyArray(randomArray);
			testQuickSort(copy, false);

			// Radix sort tests
			testRadixSort(orderedArray, true);
			copy = copyArray(randomArray);
			testRadixSort(copy, false);
		}

		outFile.close();
	}

	static void testInsertionSort(int[] array, boolean ordered) {
		Date date = new Date();
		long startTime = date.getTime();

		InsertionSort.insertionSort(array);

		date = new Date();
		long endTime = date.getTime();
		long timeToSolve = endTime - startTime; // Time in milliseconds
		output("Insertion sort " + "runtime on "
				+ (ordered ? "ordered" : "random ") + " array of length "
				+ array.length + ":  " + timeToSolve + " milliseconds");

		if (checkSorted(array)) {
			output("Insertion sort verified.");
			output();
		} else {
			output("Insertion sort failed.");
			System.exit(1);
		}
	}

	static void testQuickSort(int[] array, boolean ordered) {
		Date date = new Date();
		long startTime = date.getTime();

		QuickSort.quickSort(array);

		date = new Date();
		long endTime = date.getTime();
		long timeToSolve = endTime - startTime; // Time in milliseconds
		output("Quick sort " + "runtime on "
				+ (ordered ? "ordered" : "random ") + " array of length "
				+ array.length + ":  " + timeToSolve + " milliseconds");

		if (checkSorted(array)) {
			output("Quick sort verified.");
			output();
		} else {
			output("Quick sort failed.");
			System.exit(1);
		}
	}

	static void testRadixSort(int[] array, boolean ordered) {
		Date date = new Date();
		long startTime = date.getTime();

		RadixSort.radixSort(array);

		date = new Date();
		long endTime = date.getTime();
		long timeToSolve = endTime - startTime; // Time in milliseconds
		output("Radix sort " + "runtime on "
				+ (ordered ? "ordered" : "random ") + " array of length "
				+ array.length + ":  " + timeToSolve + " milliseconds");

		if (checkSorted(array)) {
			output("Radix sort verified.");
			output();
		} else {
			output("Radix sort failed.");
			System.exit(1);
		}
	}

	static int[] generateRandom(int n)
	// Generate an array of n random integers.
	{
		Random generator = new Random();
		int[] array = new int[n];

		for (int i = 0; i < n; i++) {
			array[i] = generator.nextInt();
		}

		array[10] = Integer.MIN_VALUE;

		return array;
	}

	static int[] generateOrdered(int n)
	// Generate an array consisting of the integers 0, 1, 2, ..., n-1.
	{
		int[] array = new int[n];

		for (int i = 0; i < n; i++) {
			array[i] = i;
		}

		return array;
	}

	static int[] copyArray(int[] array) {
		int n = array.length;
		int[] returnVal = new int[n];

		for (int i = 0; i < n; i++) {
			returnVal[i] = array[i];
		}

		return returnVal;
	}

	static boolean checkSorted(int[] array) {
		int n = array.length;
		for (int i = 0; i <= n - 2; i++) {
			if (array[i] > array[i + 1]) {
				return false;
			}
		}

		return true;
	}

	static void displayArray(int[] array) {
		for (int val : array) {
			System.out.print(" " + val);
		}
		System.out.println();
	}

	static void output(String s) {
		System.out.println(s);
		outFile.println(s);
	}

	static void output() {
		output("");
	}
}
